
// 46.全排列
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        // 使用DFS来实现
        int n = nums.size();

        vector<vector<int>> ret ;
        vector<int> each ;
        unordered_set<int> vist;
        function<void(int)> dfs = [&](int pos)
        {
            if(pos == n) 
            {
                ret.push_back(each);
                return;
            }

            for(int i = 0 ; i < n ; i++)
            {
                if(!vist.count(i))
                {
                    vist.insert(i);
                    each.push_back(nums[i]);
                    dfs(pos + 1);
                    each.pop_back();
                    vist.erase(i);
                }
            }
        };
        dfs(0);
        return ret;
    }
};